|
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers. In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by Euclid's algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant. The similarity between the integer GCD and the polynomial GCD allows us to extend to univariate polynomials all the properties that may be deduced from Euclid's algorithm and Euclidean division. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the roots of the GCD of two polynomials are the common roots of the two polynomials, and this allows to get information on the roots without computing them. For example, the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow to compute the square-free factorization of the polynomial, which provides polynomials whose roots are the roots of a given multiplicity. The greatest common divisor may be defined and exists, more generally, for multivariate polynomials over a field or the ring of integers, and also over a unique factorization domain. There exist algorithms to compute them as soon as one has a GCD algorithm in the ring of coefficients. These algorithms proceed by a recursion on the number of variables to reduce the problem to a variant of Euclid's algorithm. They are a fundamental tool in computer algebra, because computer algebra systems use them systematically to simplify fractions. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need of efficiency of computer algebra systems. ==General definition== Let ''p'' and ''q'' be polynomials with coefficients in an integral domain ''F'', typically a field or the integers. A greatest common divisor of ''p'' and ''q'' is a polynomial ''d'' that divides ''p'' and ''q'' and such that every common divisor of ''p'' and ''q'' also divides ''d''. Every pair of polynomials (not both zero) has a GCD if and only if ''F'' is a unique factorization domain. If ''F'' is a field and ''p'' and ''q'' are not both zero, ''d'' is a greatest common divisor if and only if it divides both ''p'' and ''q'' and it has the greatest degree among the polynomials having this property. If ''p'' = ''q'' = 0, the GCD is 0. However, some authors consider that it is not defined in this case. The greatest common divisor of ''p'' and ''q'' is usually denoted "gcd(''p'', ''q'')". The greatest common divisor is not unique: if ''d'' is a GCD of ''p'' and ''q'', then the polynomial ''f'' is another GCD if and only if there is an invertible element ''u'' of ''F'' such that : and :. In other words, the GCD is unique up to the multiplication by an invertible constant. In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive (there is another one, which is its opposite). With this convention, the GCD of two integers is also the greatest (for the usual ordering) common divisor. When one want to settle this indetermination in the polynomial case, one lacks of a natural total order. Therefore, one chooses once for all a particular GCD that is then called ''the'' greatest common divisor. For univariate polynomials over a field, this is usually the unique GCD which is monic (that is has 1 as coefficient of the highest degree). In more general cases, there is no general convention and above indetermination is usually kept. Therefore, equalities like ''d'' = gcd(''p'', ''q'') or gcd(''p'', ''q'') = gcd(''r'', ''s'') are usual abuses of notation which should be read "''d'' is a GCD of ''p'' and ''q''" and "''p'', ''q'' has the same set of GCD as ''r'', ''s''". In particular, gcd(''p'', ''q'') = 1 means that the invertible constants are the only common divisors, and thus that ''p'' and ''q'' are coprime. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polynomial greatest common divisor」の詳細全文を読む スポンサード リンク
|